home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / dejagnu.lha / dejagnu-1.0.1 / tcl / tclHash.h < prev    next >
C/C++ Source or Header  |  1993-02-13  |  5KB  |  147 lines
  1. /*
  2.  * tclHash.h --
  3.  *
  4.  *    This header file declares the facilities provided by the
  5.  *    Tcl hash table procedures.
  6.  *
  7.  * Copyright 1991 Regents of the University of California
  8.  * Permission to use, copy, modify, and distribute this
  9.  * software and its documentation for any purpose and without
  10.  * fee is hereby granted, provided that the above copyright
  11.  * notice appear in all copies.  The University of California
  12.  * makes no representations about the suitability of this
  13.  * software for any purpose.  It is provided "as is" without
  14.  * express or implied warranty.
  15.  *
  16.  */
  17.  
  18. #ifndef _TCLHASH
  19. #define _TCLHASH
  20.  
  21. #ifndef _TCL
  22. #include <tcl.h>
  23. #endif
  24.  
  25. /*
  26.  * Structure definition for an entry in a hash table.  No-one outside
  27.  * Tcl should access any of these fields directly;  use the macros
  28.  * defined below.
  29.  */
  30.  
  31. typedef struct Tcl_HashEntry {
  32.     struct Tcl_HashEntry *nextPtr;    /* Pointer to next entry in this
  33.                      * hash bucket, or NULL for end of
  34.                      * chain. */
  35.     struct Tcl_HashTable *tablePtr;    /* Pointer to table containing entry. */
  36.     struct Tcl_HashEntry **bucketPtr;    /* Pointer to bucket that points to
  37.                      * first entry in this entry's chain:
  38.                      * used for deleting the entry. */
  39.     ClientData clientData;        /* Application stores something here
  40.                      * with Tcl_SetHashValue. */
  41.     union {                /* Key has one of these forms: */
  42.     char *oneWordValue;        /* One-word value for key. */
  43.     int words[1];            /* Multiple integer words for key.
  44.                      * The actual size will be as large
  45.                      * as necessary for this table's
  46.                      * keys. */
  47.     char string[4];            /* String for key.  The actual size
  48.                      * will be as large as needed to hold
  49.                      * the key. */
  50.     } key;                /* MUST BE LAST FIELD IN RECORD!! */
  51. } Tcl_HashEntry;
  52.  
  53. /*
  54.  * Structure definition for a hash table.  Must be in tcl.h so clients
  55.  * can allocate space for these structures, but clients should never
  56.  * access any fields in this structure.
  57.  */
  58.  
  59. #define TCL_SMALL_HASH_TABLE 4
  60. typedef struct Tcl_HashTable {
  61.     Tcl_HashEntry **buckets;        /* Pointer to bucket array.  Each
  62.                      * element points to first entry in
  63.                      * bucket's hash chain, or NULL. */
  64.     Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE];
  65.                     /* Bucket array used for small tables
  66.                      * (to avoid mallocs and frees). */
  67.     int numBuckets;            /* Total number of buckets allocated
  68.                      * at **bucketPtr. */
  69.     int numEntries;            /* Total number of entries present
  70.                      * in table. */
  71.     int rebuildSize;            /* Enlarge table when numEntries gets
  72.                      * to be this large. */
  73.     int downShift;            /* Shift count used in hashing
  74.                      * function.  Designed to use high-
  75.                      * order bits of randomized keys. */
  76.     int mask;                /* Mask value used in hashing
  77.                      * function. */
  78.     int keyType;            /* Type of keys used in this table. 
  79.                      * It's either TCL_STRING_KEYS,
  80.                      * TCL_ONE_WORD_KEYS, or an integer
  81.                      * giving the number of ints in a
  82.                      */
  83.     Tcl_HashEntry *(*findProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
  84.         char *key));
  85.     Tcl_HashEntry *(*createProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
  86.         char *key, int *newPtr));
  87. } Tcl_HashTable;
  88.  
  89. /*
  90.  * Structure definition for information used to keep track of searches
  91.  * through hash tables:
  92.  */
  93.  
  94. typedef struct Tcl_HashSearch {
  95.     Tcl_HashTable *tablePtr;        /* Table being searched. */
  96.     int nextIndex;            /* Index of next bucket to be
  97.                      * enumerated after present one. */
  98.     Tcl_HashEntry *nextEntryPtr;    /* Next entry to be enumerated in the
  99.                      * the current bucket. */
  100. } Tcl_HashSearch;
  101.  
  102. /*
  103.  * Acceptable key types for hash tables:
  104.  */
  105.  
  106. #define TCL_STRING_KEYS        0
  107. #define TCL_ONE_WORD_KEYS    1
  108.  
  109. /*
  110.  * Macros for clients to use to access fields of hash entries:
  111.  */
  112.  
  113. #define Tcl_GetHashValue(h) ((h)->clientData)
  114. #define Tcl_SetHashValue(h, value) ((h)->clientData = (ClientData) (value))
  115. #define Tcl_GetHashKey(tablePtr, h) \
  116.     ((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS) ? (h)->key.oneWordValue \
  117.                         : (h)->key.string))
  118.  
  119. /*
  120.  * Macros to use for clients to use to invoke find and create procedures
  121.  * for hash tables:
  122.  */
  123.  
  124. #define Tcl_FindHashEntry(tablePtr, key) \
  125.     (*((tablePtr)->findProc))(tablePtr, key)
  126. #define Tcl_CreateHashEntry(tablePtr, key, newPtr) \
  127.     (*((tablePtr)->createProc))(tablePtr, key, newPtr)
  128.  
  129. /*
  130.  * Exported procedures:
  131.  */
  132.  
  133. extern void        Tcl_DeleteHashEntry _ANSI_ARGS_((
  134.                 Tcl_HashEntry *entryPtr));
  135. extern void        Tcl_DeleteHashTable _ANSI_ARGS_((
  136.                 Tcl_HashTable *tablePtr));
  137. extern Tcl_HashEntry *    Tcl_FirstHashEntry _ANSI_ARGS_((
  138.                 Tcl_HashTable *tablePtr,
  139.                 Tcl_HashSearch *searchPtr));
  140. extern char *        Tcl_HashStats _ANSI_ARGS_((Tcl_HashTable *tablePtr));
  141. extern void        Tcl_InitHashTable _ANSI_ARGS_((Tcl_HashTable *tablePtr,
  142.                 int keyType));
  143. extern Tcl_HashEntry *    Tcl_NextHashEntry _ANSI_ARGS_((
  144.                 Tcl_HashSearch *searchPtr));
  145.  
  146. #endif /* _TCLHASH */
  147.